package com.shixianchen.study.day3;

/**
 * @author ShiXianChen
 * @version V1.0.0
 * @Description TODO
 * @date 2022/10/31 23:50
 */
public class Code06_BursBalloons {

    public static int maxScore(int[] arr){
        int[] help = new int[arr.length + 2];
        help[0] = 1;
        help[help.length-1] = 1;
        for (int i = 1; i < help.length-1; i++) {
            help[i] = arr[i-1];
        }
        return process(help,1,help.length-2);
    }

    private static int process(int[] help, int L, int R) {

        //只剩一个气球
        if (L == R){
            return help[L-1] * help[L] *help[R+1];
        }

        //不止一个气球
        //分可能性
        //最后打包 L位置上的气球

        int p1 = process(help,L+1,R) + help[L-1] * help[L] *help[R+1];

        //最后打包 R 位置上的气球

        int p2 = process(help,L,R-1) + help[L-1] *help[R] * help[R+1];

        int ans = Math.max(p1,p2);

        //打爆中间位置的气球

        for (int mid = L+1; mid < R; mid ++ ){
            //
            int cur = process(help,L,mid-1)+
                    process(help,mid+1,R) +
                    help[L-1] * help[mid] *help[R+1];
            ans = Math.max(ans,cur);
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{2,3,48,7,99,1,3,77};
        System.out.println("maxScore(arr) = " + maxScore(arr));

    }
}
